from tools_algorithm import *


class Solution:
    def numberOfCombinations(self, num: str) -> int:
        n = len(num)
        f = [[0] * (n + 1) for _ in range(n + 1)]
        for i in range(n - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                f[i][j] = f[i + 1][j + 1] + 1 if num[i] == num[j] else 0
        nums = list(map(int, num))
        dp = [[0] * (n + 1) for _ in range(n)]
        for i, v in enumerate(nums):
            if v != 0:
                tot = 0
                for j in range(1, i + 1):
                    la = i - j
                    if la < 0:
                        dp[i][j] = 1
                    elif nums[la] != 0 and i + j - 1 < n:
                        if f[la][i] >= j or (
                            i + f[la][i] < n
                            and nums[la + f[la][i]] < nums[i + f[la][i]]
                        ):
                            dp[i][j] += dp[la][j] + tot
                        tot += dp[la][j]
                for j in range(i + 1, n):
                    dp[i][j] += tot
        ans = 0
        for i in range(n):
            ans += dp[i][n - i]
        return ans


s = Solution()
print(s.numberOfCombinations("327"))
print(s.numberOfCombinations("1121121"))


# def lcp(nums):
#     n = len(nums) + 1
#     f = [[0] * n for _ in range(n)]
#     for i in range(1, n):
#         for j in range(1, n):
#             f[i][j] = f[i - 1][j - 1] + 1 if nums[i - 1] == nums[j - 1] else 0
#     return f


# a = lcp("aabaab")
# for r in a:
#     print(r)
# print(a[3][4])
